package 动态规划.钱币组合问题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 322. 零钱兑换
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 *
 *  思路：采用一维动态规划
 *  1：初始化dp[]数组，其中dp[i]表示组成金额i所需的最少硬币数。
 *  2：状态转移方程的编写：对于每个金额i，遍历所有的硬币面额coin，如果 coin <= i, 则dp[i] = min(dp[i], dp[i - coin] + 1)，
 *  即当前金额的最少硬币数可以由i - coin金额的最优解加上一个硬币得到。
 *  3：初始化：初始化：dp[0] = 0（组成0元不需要硬币），其他金额初始化为一个较大的值（如amount + 1），表示暂时无法组成 （因为要取最小值）
 *  4:边界处理：处理金额为0、硬币数组为空或长度为0的情况。
 *
 */
public class L_322 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0){
            return 0;
        }
        if (coins == null || coins.length == 0){
            return -1;
        }
        // 对coin数组进行排序
        Arrays.sort(coins);
        // 定义dp状态数组
        int [] dp = new int[amount+1];
        Arrays.fill(dp, amount+1); // 初始化dp数组，将所有值初始化为一个较大的值，表示暂时无法组成
        dp[0] = 0; // 组成0元不需要硬币，初始化为0
        for (int i = 1; i <= amount ; i++) {
            for (int coin : coins){
                if (coin > i){ // 如果当前面额coin大于i，则跳出循环
                    break;
                }
                dp[i] = Math.min(dp[i], dp[i-coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入金额：");
        int amount = scanner.nextInt();
        // 数组的录入
        System.out.println("请输入硬币数量：");
        int[] coins = new int[scanner.nextInt()];
        System.out.println("请逐个输入硬币面额：");
        for (int i = 0; i < coins.length; i++) {
            coins[i] = scanner.nextInt();
        }
        L_322 l322 = new L_322();
        int result = l322.coinChange(coins, amount);
        System.out.println("最少硬币数：" + result);
    }

}
